package 剑指offer;

public class _52两个链表的第一个公共节点 {
     public class ListNode {
     int val;
     ListNode next;
     ListNode(int x) {
         val = x;
         next = null;
    }
 }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        //1.先确认两个链表的长度
        int lengthA = getListLength(headA);
        int lengthB = getListLength(headB);

        int step = Math.abs(lengthA - lengthB);

        if(lengthA > lengthB){
            while (step > 0){
                headA = headA.next;
                step--;
            }
        }else {
            while (step > 0){
                headB = headB.next;
                step--;
            }
        }
        //2.同时向后走，边走边判定
        while (headA != null && headB != null){
            if(headA == headB){
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }

    private int getListLength(ListNode head) {
        if(head == null){
            return 0;
        }
        int length = 0;
        while (head != null){
            head = head.next;
            length++;
        }
        return length;
    }
}
